#include "myTree.h"

using namespace std;

TreeNode::TreeNode(char data = '@', TreeNode* leftChild = NULL, TreeNode* rightChild = NULL, NodeTag lTag = Link, NodeTag rTag = Link)
{
    this->data = data;
    this->leftChild = leftChild;
    this->rightChild = rightChild;
    this->lTag = lTag;
    this->rTag = rTag;
}


void TreeNode::printNode()
{
    cout << this->data;
}



MyTree::MyTree()
{
    root = new TreeNode();
    root->leftChild = NULL;
    isThread = false;
}

MyTree::MyTree(const char* initArray)
{
    int index = 0;
    isThread = false;

    root = new TreeNode();

    this->root->leftChild = _makeTree(initArray, index);
}

MyTree::MyTree(const MyTree& T)
{
    isThread = false;

    root = new TreeNode();

    this->root->leftChild = _copyTree(T.root->leftChild);
}

MyTree::~MyTree()
{
    if (!isThread)
        _releaseNode(this->root->leftChild);
    else
    {
        _releaseNode_Thr(this->root);
    }

    delete root;
    root = NULL;

}

void MyTree::preOrderTraverse()
{
    _prevOrderNode(this->root->leftChild);
}

void MyTree::inOrderTraverse()
{
    if (this->isThread)
        _inOrderNode_Thr(this->root);
    else
        _inOrderNode(this->root->leftChild);
}

void MyTree::postOrderTraverse()
{
    _postOrderNode(this->root->leftChild);
}

int MyTree::countLeaf()
{
    return _coutLeaf(this->root->leftChild);
}

int MyTree::countHeight()
{
    return _countHeight(this->root->leftChild);
}

bool MyTree::isThreadedTree()
{
    return this->isThread;
}

bool MyTree::inOrderThreading()
{
    try
    {
        this->root->rTag = Thread;
        this->root->rightChild = this->root;

        TreeNode* pre = this->root;

        if (this->root->leftChild == NULL)
        {
            this->root->lTag = Thread;
            this->root->leftChild = this->root;
        }
        else
        {
            _inThreading(this->root->leftChild, pre);
        }

        pre->rTag = Thread;
        pre->rightChild = this->root;
        this->root->rightChild = pre;
    }
    catch (const std::exception& e)
    {
        return false;
    }

    this->isThread = true;
    return true;

}

TreeNode& MyTree::locateNode(const char& v)
{
    if (this->isThread)
        return *_locateNode_Thr(v, this->root);
    else
        return *_locateNode(v, this->root->leftChild);
}

void MyTree::_prevOrderNode(TreeNode* root)
{
    TreeNode* temp = root;

    if (temp == NULL)
        return;
    else
    {
        cout << temp->data;
        _prevOrderNode(temp->leftChild);
        _prevOrderNode(temp->rightChild);
    }
}

void MyTree::_inOrderNode(TreeNode* root)
{
    TreeNode* temp = root;

    if (temp == NULL)
        return;
    else
    {
        _inOrderNode(temp->leftChild);
        cout << temp->data;
        _inOrderNode(temp->rightChild);
    }

}

void MyTree::_inOrderNode_Thr(TreeNode* root)
{
    TreeNode* temp;

    temp = root->leftChild;

    while (temp != root)
    {
        while (temp->lTag == Link)
            temp = temp->leftChild;
        cout << temp->data;
        while (temp->rTag == Thread && temp->rightChild != root)
        {
            temp = temp->rightChild;
            cout << temp->data;
        }
        temp = temp->rightChild;
    }
}

void MyTree::_postOrderNode(TreeNode* root)
{
    TreeNode* temp = root;

    if (temp == NULL)
        return;
    else
    {
        _postOrderNode(temp->leftChild);
        _postOrderNode(temp->rightChild);
        cout << temp->data;
    }

}

TreeNode* MyTree::_makeTree(const char* initArray, int& index)
{
    TreeNode* temp = NULL;

    if (initArray[index] == '@')
        return NULL;
    else
    {
        temp = new TreeNode(initArray[index]);
        temp->leftChild = _makeTree(initArray, ++index);
        temp->rightChild = _makeTree(initArray, ++index);
        return temp;
    }

}
TreeNode* MyTree::_copyTree(const TreeNode* root)
{
    TreeNode* temp = NULL;

    if (root == NULL)
        return NULL;
    else
    {
        temp = new TreeNode(root->data);
        temp->leftChild = _copyTree(root->leftChild);
        temp->rightChild = _copyTree(root->rightChild);

        return temp;
    }

}

void MyTree::_releaseNode(TreeNode* root)
{
    TreeNode* temp = root;
    if (temp == NULL)
        return;
    else
    {
        _releaseNode(temp->leftChild);
        _releaseNode(temp->rightChild);

        delete temp;
        temp = NULL;
    }

}

void MyTree::_releaseNode_Thr(TreeNode* root)
{
    TreeNode* temp = root->leftChild;
    NodeTag tempNodeTag = Link;
    TreeNode* tempRightChild;

    while (temp != root)
    {
        while (temp->lTag == Link)
            temp = temp->leftChild;
        tempNodeTag = temp->rTag;
        tempRightChild = temp->rightChild;
        delete temp;

        while (tempNodeTag == Thread && tempRightChild != root)
        {
            temp = tempRightChild;
            tempNodeTag = temp->rTag;
            tempRightChild = temp->rightChild;
            delete temp;
        }
        temp = tempRightChild;
    }
}

int MyTree::_coutLeaf(TreeNode* root)
{
    TreeNode* temp = root;

    if (temp == NULL)
        return 0;
    else if (temp->leftChild == NULL && temp->rightChild == NULL)
        return 1;
    else
        return _coutLeaf(temp->leftChild) + _coutLeaf(temp->rightChild);
}

int MyTree::_countHeight(TreeNode* root)
{
    TreeNode* temp = root;

    if (temp == NULL)
        return 0;
    else
    {
        int m = _countHeight(temp->leftChild);
        int n = _countHeight(temp->rightChild);

        return (m >= n) ? m + 1 : n + 1;
    }

}

TreeNode* MyTree::_locateNode(const char& v, TreeNode* root)
{
    TreeNode* result = NULL;
    TreeNode* temp = root;

    if (temp == NULL)
        result = NULL;
    if (temp->data == v)
        result = temp;
    else
    {
        result = _locateNode(v, temp->leftChild);
        if (result == NULL)
            result = _locateNode(v, temp->rightChild);
    }

    return result;

}

TreeNode* MyTree::_locateNode_Thr(const char& v, TreeNode* root)
{
    TreeNode* result = NULL;
    TreeNode* temp = root->leftChild;

    while (temp != root)
    {
        while (temp->lTag == Link)
            temp = temp->leftChild;
        if (temp->data == v)
        {
            result = temp;
            break;
        }
        if (result == NULL)
        {
            while (temp->rTag == Thread && temp->rightChild != root)
            {
                temp = temp->rightChild;
                if (temp->data == v)
                {
                    result = temp;
                    break;
                }
            }
            if (result == NULL)
                temp = temp->rightChild;
        }
        if (result != NULL)
            break;

    }

    return result;

}

void MyTree::_inThreading(TreeNode* root, TreeNode*& pre)
{
    TreeNode* temp = root;

    if (temp != NULL)
    {
        _inThreading(temp->leftChild, pre);
        if (temp->leftChild == NULL)
        {
            temp->lTag = Thread;
            temp->leftChild = pre;
        }
        if (pre->rightChild == NULL)
        {
            pre->rTag = Thread;
            pre->rightChild = temp;
        }

        pre = temp;
        _inThreading(temp->rightChild, pre);
    }
}

TreeNode& MyTree::preNode(const TreeNode& n)
{
    TreeNode temp = n;
    static TreeNode result;

    if (temp.lTag == Thread)
    {
        if (temp.leftChild != this->root)
            result = *temp.leftChild;
    }
    else
    {
        temp = *temp.leftChild;
        while (temp.rTag == Link)
            temp = *temp.rightChild;
        result = temp;
    }

    return result;
}

TreeNode& MyTree::nextNode(const TreeNode& n)
{
    TreeNode temp = n;
    static TreeNode result;

    if (temp.rTag == Thread)
    {
        if (temp.rightChild != root)
            result = *temp.rightChild;
    }
    else
    {
        temp = *temp.rightChild;
        while (temp.lTag == Link)
            temp = *temp.leftChild;
        result = temp;
    }

    return result;
}



HuffmanTree::HuffmanTree(const int& leafNum, const int* initArray)
{
    this->leafNum = leafNum;
    this->nodeNum = 2 * leafNum - 1;
    forest = new HuffmanTreeNode[this->nodeNum];
    int fir_min_pos, sec_min_pos;

    for (int i = 0; i < this->leafNum; i++)
    {
        forest[i].weight = initArray[i];
    }

    creatLeafTab(initArray);

    for (int i = this->leafNum; i < this->nodeNum; i++)
    {
        int fir_min = 9999, sec_min = 9999;
        fir_min_pos = sec_min_pos = -1;
        for (int j = 0; j < i; j++)
        {
            if (forest[j].parent == -1)
            {
                if (forest[j].weight < fir_min)
                {
                    sec_min = fir_min;
                    sec_min_pos = fir_min_pos;
                    fir_min = forest[j].weight;
                    fir_min_pos = j;
                }
                else if (forest[j].weight < sec_min)
                {
                    sec_min = forest[j].weight;
                    sec_min_pos = j;
                }
            }
        }

        forest[i].leftChild = fir_min_pos;
        forest[i].rightChild = sec_min_pos;
        forest[i].weight = forest[fir_min_pos].weight + forest[sec_min_pos].weight;
        forest[fir_min_pos].parent = forest[sec_min_pos].parent = i;

    }

    for (int i = 0; i < this->leafNum; i++)
    {
        leafTab[i].code = encodeLeaf(leafTab[i].order);
    }

}


void HuffmanTree::printHuffmanCodes()
{

    for (int i = 0; i < this->leafNum - 1; i++)
        cout << leafTab[i].weight << ":" << leafTab[i].code << endl;

    cout << leafTab[this->leafNum - 1].weight << ":" << leafTab[this->leafNum - 1].code << endl;
}

void HuffmanTree::creatLeafTab(const int* initArray)
{
    leafTab = new leafNode[this->leafNum];

    for (int i = 0; i < this->leafNum; i++)
    {
        leafTab[i].weight = initArray[i];
        leafTab[i].order = i;
    }

    int tempOrder = 0;


    for (int i = 0; i < this->leafNum; i++)
    {
        int max = leafTab[i].weight;
        int maxPos = i;
        for (int j = i + 1; j < this->leafNum; j++)
        {
            if (leafTab[j].weight > max)
            {
                max = leafTab[j].weight;
                maxPos = j;
            }
        }

        tempOrder = leafTab[maxPos].order;

        leafTab[maxPos].weight = leafTab[i].weight;
        leafTab[maxPos].order = leafTab[i].order;

        leafTab[i].weight = max;
        leafTab[i].order = tempOrder;
    }
}

string HuffmanTree::encodeLeaf(int index)
{
    string temp = "";
    string result = "";

    int i = index;
    int parent = -1;

    while (forest[i].parent != -1)
    {
        parent = forest[i].parent;
        if (forest[parent].leftChild == i)
            temp += '0';
        else
            temp += '1';
        i = parent;
    }

    for (int i = temp.length() - 1; i >= 0; i--)
    {
        result += temp[i];
    }

    return result;
}

